package linkedList.前缀和;

import linkedList.BaseLinkedListTest;
import po.ListNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N从链表中删去总和值为零的连续节点1171.java
 * @Description TODO https://leetcode-cn.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/
 * @createTime 2021年03月18日 14:36:00
 */
public class N从链表中删去总和值为零的连续节点1171 extends BaseLinkedListTest {

    /**
     * todo 这里要注意的是 总和  值为0的   连续  节点组成的队列。需要住的是总和  和 连续两个词，表示的是连续的n个节点，值为0就可以了。如果可以不连续，那么难度就上升好多了
     */
    public static ListNode removeZeroSumSublists(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        Map<Integer, ListNode> nodeMap = new HashMap<>();
        ListNode temp = pre;
        int num = 0, sum = 0;
        while (temp != null) {
            //todo 前k个数的和
            sum += temp.val;
            //todo 计算跟sum的和为0的值
            num = sum;
            /**
             * todo 检查map中是否存在这个值,如果存在这个值，说明从这个值开始到目前循环到的值，之间所有的节点加起来的和值为0。
             * todo 举例  1 2 3 -3 4 其中1+2=3 则前两个位置的和为3，1+2+3+(-3)=3 则前4个位置的和位3 因为第4个位置和第二个位置中间的数的值的和肯定为0
             */
            if (nodeMap.containsKey(num)) {
                //todo 找到和为0的区间的第一个节点
                temp = nodeMap.get(num).next;
                //todo 累计和为0区间的节点的值
                int val = num + temp.val;
                //todo 循环到累加的和等于一开始指定的值，则说明找到了最后的一个元素使得区间内的节点值和为0
                while (val != num) {
                    nodeMap.remove(val);
                    temp = temp.next;
                    val += temp.val;
                }
                nodeMap.get(num).next = temp.next;

            } else {
                nodeMap.put(sum, temp);
            }
            temp = temp.next;
        }
        return pre.next;
    }

    public static void main(String[] args) {
        removeZeroSumSublists(createLinkedList(1,2,3,-3,-2));
    }
}
